今天是真的头疼

T1

问题

有n个电线杆,第i个高度为h[i],在相邻的电线杆之间造电线需要的价值是abs(h[i]-h[i-1]) * C.为一根电线杆增加X高度的代价是X²,最小化代价和

n <= 10^5,h[i],C[i] <= 100;

解法

设f[i][j]表示

T2

问题

求有多少长度为N的排列,使得每个数要么比旁边两个都大,要么比旁边两个都小.

N <= 5000

解法

f[i][j]表示长度为i,最后一个数是j,且该排列p中p[i-1]>p[i]的合法方案数,g[i][j]表示长度为i,最后一个数是j,且排列中p[i-1]<p[i]的合法方案数.则f[i][j]=g[i][i-j+1].

T3

问题

有n个人参加比赛,第i个人说:有ai个人比我分数高,有bi个人比我分数低,可以有相同分数,问最多多少人说真话

n <= 100000

解法

一个人说真话代表ai+1搭配n-bi的人的分数都是一样的.如果我们把它看成一段线段,那么在这n条线段中,相交且不重合的线段一定不能同时成为真话.
所以问题就转化为选出尽量多的不想交或完全重合的线段,

T4

问题

祖玛,消掉的条件是个数>=k,给出初始局面,要求插入一些颜色的尽可能少的球,使得原始局面依次插入球后全部消掉 N <= 100

解法

看起来就很像区间DP,f[l][r]表示将[l,r]消掉需要的最少球数.通常选择[l,r]之间的k,先消掉[l,k],再消[k,r].但是因为消掉以后两端会接在一起,所以普通的区间DP无法完成.

我们可以人为规定从左到右消掉序列.考虑一段区间的左边第一个数可能是怎么消掉的.

1. 人为直接加球消掉
2. 后面的消掉以后这个球和后面的拼在一起消掉了

f[i][j][k]表示消掉[i,j],前面已经插入了k个和a[l]一样的球的最小花费

转移:

1. f[l][r][k] = f[l][x][k] + f[x+1][r][0]
2. f[l][r][k] = f[l][r][k-1] + 1
3. f[l][r][k] = f[l+1][x-1][0] + f[x][r][k+1]

   T5

   问题

   有一个人在2 * n的网格上种蘑菇,(i,j)位置上每单位时间会增长v[i,j]的蘑菇.一个人从(1,1),每单位时间移动一个格子,且访问每个格子一次且仅一次,求他最多采多少蘑菇

   解法

   本题首先要注意的是经过每个点一次且仅一次.对于任意一个前缀,它的横向走的步数应该少于纵向走的步数.

设f[i][0]表示按照”蛇形”走完了前i格,f[i][1]表示按照U形走完了前i格.

T6

问题

一开始有一个全部都是0的长度为n的序列.

现在要对这个序列进行若干轮操作,每一轮你都要选择这个序列的一个权值相同的连续子序列,然后把除了第一个和最后一个之外的数全部+1.

在进行了操作后,这个序列的若干项遗失了.问有多少种填数方法,使得它是合法的.

1 <= n <= 10000, 1 <= h[i] <= 10000

解法

考虑逆操作,选择[l,r],将除了头尾之外的都-1,要求-1后这一段权值相等.

T7

问题

求n个点(带标号)的连通图个数,答案对998244353取模

解法

如果不要求连通(任意图),那么就是2^C(n,2)次.
可以通过减去不合法的来求出连通图的个数.不合法就意味着图被分成了若干块.令f[n]表示大小为n的连通图个数.则f[n] = 2^C(n,2)-不连通图个数(g[n]).如何求g[n]呢.考虑1号点所在连通块大小为i,则剩下了n-i个点与这个块不连通.这i个点内部连边方案为f[i]种.i和n-i个点之间连边方案为1,即不连边.剩下的n-i个点则随意连都不影响答案,那么其连边方案为2^C(n-i,2)种.然而本题要求有编号,这i个点不一定是2到i号(提前已指定1号点的联通块大小为i).,因此还要乘上C(n-i,i-1).

T8

问题

求n个点(带标号)的欧拉图个数,答案对998244353取模.
※欧拉图:连通的存在一条欧拉回路的图

解法

容斥,先求出每个点度数都是偶数的图的个数,然后再减去不连通的这种图的个数.

先取出一个点,剩下n-1个点内部随便连的话将成为2^C(n-1,2).但是这其中将会有一些度数为奇数的点,这时候就将拿出来的1号点向那些点连边.这时候1号点呢?一定是偶数度数.因为此时其他所有的点都是偶数度数,所以1不可能是奇数度数.设f[n]表示大小为n,欧拉图的方案数.f[n] = 2^[(n-1) * (n-2) / 2]-g[n].g[n]=Σi from 1 to n-1,g[i] * (n - i - 1) * (n - i - 2) * C(

T9

问题

有n个小朋友在玩游戏.有一个环,环上有2^m个位置,标号从0开始.

这n个小朋友每个人在时刻0在某个位置上,每隔一秒,他们都会顺时针往下移动一位.即如果原来在位置x,下一秒会在位置(x+1)%2^m.

问,在[1,T]这些时刻里,有多少个时刻他们的位置编号的异或和为S?

n <= 10^5,m <= 50,T <= 10^16,S <= 2^m.

解法

假设T=2^m - 1,f[i][j]表示已经确定了T的后i位,有j个数进位了(由此可知有哪些仅为了,因为进位的一定是%2^m的前j位)的方案数.枚举T的第i位是0还是1,就可以知道每个数在这一位是什么,检验一下XOR起来是不是S的这一位,是就合法,否则不合法….████████████████[数据删除]